package cn.hesion.leetcode;
/**
 * ClassName: WaysToSplit <br/>
 * Description: <br/>
 * date: 2022/6/8 20:19<br/>
 *
 * @author Hesion<br />
 * @version
 * @since JDK 1.8
 */

/**
 * 1712. 将数组分成三个子数组的方案数
 * @author: hesion
 * @create: 2022-06-08 20:19
 **/
public class WaysToSplit {
    public int waysToSplit(int[] sum) {
        int mod = 1000000007;
        int n = sum.length;
        int i;
        for(i=1;i<n;++i){
            sum[i] += sum[i-1];
        }
        long ans=0;
        for(i=1;i<sum.length-1;++i){
            int l=0;
            int r=i-1;
            int rightest = -1;

            while(l<=r){
                int mid = (l+r)>>1;
                if(sum[mid] <= sum[i]-sum[mid]){
                    l = mid+1;
                    rightest = mid;
                }else{
                    r=mid-1;
                }
            }
            if(rightest==-1){
                continue;
            }

            l=0;
            r=rightest;
            int leftest = -1;
            while(l<=r){
                int mid = (l+r)>>1;
                if(sum[i]-sum[mid]<=sum[n-1]-sum[i]){
                    r = mid-1;
                    leftest=mid;
                }else{
                    l = mid+1;
                }
            }

            if(leftest != -1){
                ans+=(rightest-leftest+1);
                ans %=mod;
            }
        }
        return (int)ans;
    }

    public static void main(String[] args) {
        int i = new WaysToSplit().waysToSplit(
                new int[]{
                        1, 2, 2, 2, 5, 0
                }
        );
        System.out.println(i);
    }
}
